#!/usr/bin/env python

import sys, os, math, itertools
import cPickle as pickle

os.environ['DJANGO_SETTINGS_MODULE'] = 'settings'
from gtfs.models import *
from django.db.models import Max, Min
from django.contrib.gis.geos import Point, LineString
from django.db import transaction

# crimed from http://docs.python.org/library/itertools.html
def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = itertools.tee(iterable)
    next(b, None)
    return itertools.izip(a, b)

class Pair(object):
    def __init__(self, p1, p2):
        self.p1, self.p2 = self.compare_points(p1, p2)
        self.trip_set = set()

    def __eq__(self, p):
        rv = (p.p1 == self.p1).all() and (p.p2 == self.p2).all()
        #        print self.p1, self.p2, p.p1, p.p2, "eq", rv
        return rv

    def __hash__(self):
        hl = lambda l: reduce(lambda a, b: hash(a) >> 4 ^ hash(b), l)
        return hl((hl(self.p1), hl(self.p2)))

    def __repr__(self):
        return 'pair: %s %s' % (str(self.p1), str(self.p2))

    def get_p1(self):
        if self.reverse:
            return self.p2
        else:
            return self.p1

    def get_p2(self):
        if self.reverse:
            return self.p1
        else:
            return self.p2

    def compare_points(self, p1, p2):
        def _c():
            if p1[0] < p2[0]:
                return False
            elif p1[0] > p2[0]:
                return True
            elif p1[1] < p2[1]:
                return False
            elif p1[1] > p2[1]:
                return True
            else:
                return False
        self.reverse = _c()
        tp = (p1, p2)
        if self.reverse:
            return tp[1], tp[0]
        else:
            return tp

    def add_trip_set(self, ts):
        self.trip_set = self.trip_set.union(ts)

class PairFactory(object):
    "issue uniques pairs when given a line string object"
    def __init__(self):
        self._next_id = 1 # must be positive, > 0
        self.pair_to_id = {}
        self.id_to_pair = {}
        self.seen = 0

    def makepairs(self, line_string):
        for i, pair in enumerate(pairwise(line_string.array)):
            p = Pair(*pair)
            if not self.pair_to_id.has_key(p):
                self.pair_to_id[p] = self._next_id
                self.id_to_pair[self._next_id] = p
                self._next_id += 1
            pair_id = self.pair_to_id[p]
            if p.reverse:
                pair_id = -pair_id
            yield pair_id
        self.seen += (i + 1)

    def pair_from_id(self, id):
        rv = self.id_to_pair[abs(id)]
        rv.reverse = id < 0
        return rv

    def represent(self, pair_ids):
        points = []
        pair = None
        huge = 1 << 30
        min_lat, max_lat = huge, -huge
        min_lon, max_lon = huge, -huge

        def pairs_to_points():
            pair = None
            for pair_id in pair_ids:
                pair = self.pair_from_id(pair_id)
                yield pair.get_p1()

            if pair is not None:
                yield pair.get_p2()
            
        points = list(pairs_to_points())

        for pair_id in pair_ids:
            pair = self.pair_from_id(pair_id)
            if pair.get_p1() not in points:
                raise Exception("p1", pair.get_p1())
            if pair.get_p2() not in points:
                raise Exception("p2", pair.get_p1())

        for lat, lon in points:
            if lat < min_lat: min_lat = lat
            if lat > max_lat: max_lat = lat
            if lon < min_lon: min_lon = lon
            if lon > max_lon: max_lon = lon

        line_string = LineString(map(tuple, points))
        return { 'line_string' : line_string,
                 'min_lat' : min_lat,
                 'max_lat' : max_lat,
                 'min_lon' : min_lon,
                 'max_lon' : max_lon }

class Line(object):
    def __init__(self, factory, from_shape_id, line_string, make_pair_ids, trip_set):
        self.factory = factory
        self.from_shape_id = from_shape_id
        self.line_string = line_string
        self.pair_ids = list(make_pair_ids(line_string))
#        xc = factory.represent(self.pair_ids)['line_string']
#        self.check_linestrings(self.line_string, xc)
        for pair_id in self.pair_ids:
            factory.pair_from_id(pair_id).add_trip_set(trip_set)
        self.segments = []

#     def check_linestrings(self, a, b):
#         a = map(list, a)
#         b = map(list, b)
#         def write_array(f, a):
#             fd = open(f, 'w')
#             for i in a:
#                 fd.write("%s\n" % (repr(i)))
#             fd.close()
#         if a != b:
#             print len(a), len(b)
#             write_array('1.txt', a)
#             write_array('2.txt', b)
#             raise Exception('mismatch')

    def reduce(self, segments_from_pair, add_segment):
        idx = 0
        def existing_segment():
            check = self.pair_ids[idx:]
            for segment in segments_from_pair(self.pair_ids[idx]):
                if segment.matches(check):
                    return segment
            return None

        def new_segment():
            segment_pair_ids = [self.pair_ids[idx]]
            first_pair = self.factory.pair_from_id(segment_pair_ids[0])
            for pair_id in self.pair_ids[idx+1:]:
                pair = self.factory.pair_from_id(pair_id)
                if pair.trip_set != first_pair.trip_set:
                    break
                segment_pair_ids.append(pair_id)
            return add_segment(segment_pair_ids)
        
        while idx < len(self.pair_ids):
            segment = existing_segment() or new_segment()
            assert(segment is not None)
            self.segments.append(segment)
            idx += len(segment)

        cc = []
        print self.pair_ids
        for i, segment in enumerate(self.segments):
            print i, list(segment.pair_iter())
            print id(segment), segment.pair_ids, segment.represent(self.factory)['line_string']
            cc += list(segment.pair_iter())
        if cc != self.pair_ids:
            print len(cc)
            print len(self.pair_ids)
            raise Exception("yikes")

    def store(self):
        for idx, segment in enumerate(self.segments):
            print idx, segment.obj().line_string
            ss = ShapeSegments(shape=Shape.objects.get(id=self.from_shape_id),
                               segment=segment.obj(),
                               reverse=segment.reversed(),
                               position=idx)
            ss.save()

class Lines(object):
    def __init__(self, dataset):
        self.lines = []
        self.factory = PairFactory()
        print "generating Lines"
##        shapes = [Shape.objects.get(text_id=str(t)) for t in xrange(20918, 20920)]
        shapes = Shape.objects.all()
        for i, shape in enumerate(shapes):
            trip_set = set((trip.id for trip in 
                            shape.trip_set.filter(service__dataset=dataset)))
            if not trip_set:
                continue
            self.lines.append(Line(self.factory,
                                   shape.id,
                                   shape.line_string,
                                   self.factory.makepairs,
                                   trip_set))
            sys.stderr.write('.')
            sys.stderr.flush()
##            if i > 50: break
        print "\nsummary: ", self.factory.seen, len(self.factory.pair_to_id)

class LineSegment(object):
    def __init__(self, pair_ids):
        self.pair_ids = pair_ids
        self._db_obj = None

    def __len__(self):
        return len(self.pair_ids)

    def obj(self):
        return self._db_obj

    def pair_iter(self, reverse=False):
        if reverse:
            return reversed([-1 * t for t in self.pair_ids])
        else:
            return iter(self.pair_ids)
    
    def represent(self, factory, reverse=False):
        return factory.represent(self.pair_iter(reverse))

    def matches(self, pair_ids, reverse=False):
        def iter_contains(needle, haystack):
            while 1:
                try:
                    v2 = needle.next()
                except StopIteration:
                    return True
                try:
                    v1 = haystack.next()
                except StopIteration:
                    return False
                if v1 != v2:
                    return False
        it = self.pair_iter(reverse)
        return iter_contains(it, iter(pair_ids))

    def store(self, factory, dataset):
        representation = self.represent(factory, True)
        print factory.pair_from_id(-1)
        print "repr", id(self), self.pair_ids, representation['line_string']
        self._db_obj = Segment(dataset=dataset,
                               **representation)
        self._db_obj.save()

    def __eq__(self, other):
        return self.pair_ids == other.pair_ids or \
            list(reversed(self.pair_ids)) == other.pair_ids

    def reversed(self):
        return False

class ReversedLineSegment(object):
    def __init__(self, segment):
        self.segment = segment

    def __len__(self):
        return self.segment.__len__()

    def obj(self):
        return self.segment.obj()

    def reversed(self):
        return True

    def pair_iter(self):
        return self.segment.pair_iter(reverse=True)

    def represent(self, factory):
        return self.segment.represent(factory, reverse=True)

    def matches(self, pair_ids):
        return self.segment.matches(pair_ids, reverse=True)

class TripSegments(object):
    def __init__(self, lines):
        self.lines = lines
        self.segments = []
        self.starts = {}
        self.ends = {}
        self.et = ()

    def add_segment(self, pair_ids):
        segment = LineSegment(pair_ids)
        start, end = pair_ids[0], pair_ids[-1]

        def link(h, pair_id):
            if not h.has_key(pair_id):
                h[pair_id] = []
            for other in h[pair_id]:
                if other == segment:
                    raise Exception("insert of duplicate segment")
            h[pair_id].append(segment)

        self.segments.append(segment)
        link(self.starts, start)
        link(self.ends, end)
        return segment

    def get_segments(self, pair):
        if self.starts.has_key(pair):
            return self.starts[pair]
        elif self.ends.has_key(pair):
            return map(ReversedLineSegment, self.ends[pair])
        else:
            return self.et

    def generate(self):
        print "generating segments"
        for line in self.lines.lines:
            line.reduce(self.get_segments, self.add_segment)
            sys.stderr.write('.')
            sys.stderr.flush()
        print "\n%d segments generated" % len(self.segments)

    @transaction.commit_on_success
    def store(self, dataset):
        print "Storing"
        print len(self.segments), "segments"
        
        # cross check
#        for start in self.starts.keys():
#            check = self.starts[start]
#            if len(check) < 2:
#                continue
#            print "check", start, check
#             for a, b in itertools.permutations(check, 2):
#                 if a == b:
#                     print "Something fishy"
#                     print a.pair_ids
#                     print b.pair_ids

        for segment in self.segments:
            segment.store(self.lines.factory, dataset)

        for line in self.lines.lines:
            line.store()

if __name__ == '__main__':
    source = sys.argv[1]
    dataset = Dataset.objects.get(source=source)
    ts = TripSegments(Lines(dataset))
    ts.generate()
    ts.store(dataset)

